package dataStructs.tree;


/**
 * @author Jonny Long
 * @date 2021/3/7 12:51
 */
public class BinaryTree {
    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    public Node getRoot() {
        return root;
    }

    // 先序遍历
    public void preOrder(Node current) {
        if (current != null) {
            System.out.println(current);
            preOrder(current.getLeft());
            preOrder(current.getRight());
        }
    }

    // 中序遍历
    public void infixOrder(Node current) {
        if (current != null) {
            infixOrder(current.getLeft());
            System.out.println(current);
            infixOrder(current.getRight());
        }
    }

    // 后序遍历
    public void postOrder(Node current) {
        if (current != null) {
            postOrder(current.getLeft());
            postOrder(current.getRight());
            System.out.println(current);
        }
    }

    // 递归前序查找
    public Node preOrderSearch(Node current, int no) {
        // 比较当前结点是不是
        if (current.getNo() == no) {
            return current;
        }
        Node res = null;
        // 1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
        // 2.如果左递归前序查找，找到结点，则返回
        if (current.getLeft() != null) {
            res = preOrderSearch(current.getLeft(), no);
        }
        if (res != null) {
            return res;
        }
        // 1.左递归前序查找，找到结点，则返回，否继续判断，
        // 2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
        if (current.getRight() != null) {
            res = preOrderSearch(current.getRight(), no);
        }
        return res;
    }

    // 递归中序查找
    public Node infixOrderSearch(Node current, int no) {
        Node res = null;
        if (current.getLeft() != null) {
            res = infixOrderSearch(current.getLeft(), no);
        }
        if (res != null) {
            return res;
        }
        if (current.getNo() == no) {
            return current;
        }
        if (current.getRight() != null) {
            res = infixOrderSearch(current.getRight(), no);
        }
        return res;
    }

    // 递归后序查找
    public Node postOrderSearch(Node current, int no) {
        Node res = null;
        // 左子树
        if (current.getLeft() != null) {
            res = postOrderSearch(current.getLeft(), no);
        }
        if (res != null) {
            return res;
        }
        // 右子树
        if (current.getRight() != null) {
            res = postOrderSearch(current.getRight(), no);
        }
        if (res != null) {
            return res;
        }
        if (current.getNo() == no) {
            return current;
        }
        return res;
    }

    // 二叉树深度
    public int depthTree(Node current) {
        int m, n;
        if (current == null) {
            return 0;
        }
        m = depthTree(current.getLeft());
        n = depthTree(current.getRight());
        return Math.max(m, n) + 1;
    }

    /**
     * 删除操作：
     * 如果删除的节点是叶子节点，则删除该节点
     * 如果删除的节点是非叶子节点，则删除该子树
     * 1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.
     * 2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.getLeft() = null; 并且就返回(结束递归删除)
     * 3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.getRight()= null ;并且就返回(结束递归删除)
     * 4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
     * 5. 如果第4步也没有删除结点，则应当向右子树进行递归删除.
     */
    public void delNode(Node current, int no) {
        if (current.getLeft() != null && current.getLeft().getNo() == no) {
            current.setLeft(null);
            return;
        }
        if (current.getRight() != null && current.getRight().getNo() == no) {
            current.setRight(null);
            return;
        }
        if (current.getLeft() != null) {
            delNode(current.getLeft(), no);
        }
        if (current.getLeft() != null) {
            delNode(current.getRight(), no);
        }
    }
}
